The exchange of value is increasingly moving into the digital realm. Everything from game points, credits, frequent flyer miles, to more traditional financial transactions and records are being tracked digitally. Most of these digital objects are tracked by an issuing authority or central record keeping entity. Keeping track of transferrable ownership rights historically required a central record keeping authority trusted by those exchanging said ownership rights. The record keeping authority typically verifies property owners via some form of identification or signature and records all valid property transfers to maintain a record of the current state of ownership. Banks using digital representations of money are trusted to verify identities and keep accurate records of deposits and transfers. A company issuing reward points or game points would also fulfill this role.
There are times, however, when relying on a central authority is not desirable. Participants who rely on these digital tokens to be tracked and recorded accurately may feel that a central authority is a single point of potential failure and a single point of trust. This authority may be subject to various internal or external pressures or corruption. There is a need and market for systems of value tracking that function in a more peer to peer (also referred to herein as peer-to-peer and P2P) fashion or where participants have greater control over the record keeping system rather than a single record keeper. For example, crypto-currencies (also referred to herein as cryptocurrency), such as Bitcoin promoted by Bitcoin.com (“Bitcoin”), track digital tokens in a more decentralized manner. Crypto-currencies use cryptographic digital signatures in place of traditional methods of identity verification as proof of ownership of digital assets.
Tracking digital tokens over a peer-to-peer network without a central record keeping authority however, presents a considerable technical challenge. The challenge can be broken into a two part problem of achieving verifiable signatures for transfers and maintaining a ledger that is consistent among all participants.
The application of public key cryptography solves one part of the challenge of a peer-to-peer digital currency. Public key cryptography signing algorithms allow for unambiguous digital signatures. A private cryptographic key is a large random number generated locally on a user's computer such that it is known only to that user. A public key can be derived from the private key. As long as the private key is kept secret, any signature produced using the private key serves as proof that the signer is the same party that originally published the public key. In addition to proving the source of a signed message, the signature also ensures that no data in the message can be lost or changed without invalidating the signature. Public keys can be recorded in a ledger of ownership rights. Digital assets can be associated with these public keys such that the public keys serve as the digital representation of the owner of the assets. A transfer of ownership of a digital asset from one public key to another can be signed with the secret private key of the sender to prove the authenticity and integrity of the message.
Unambiguous digital signatures, while useful, do not fully solve the problem of verifiable trusted record keeping. If we imagine an initial public ledger with an agreed upon list of public keys and associated digital assets, any transfers would need to be signed with the corresponding private key known only to the sender in order to be accepted. Any central record keeping authority tasked with recording changes and transfers to the ledger would have no way to forge such a transfer if it was not initiated and signed by the sender. However, many potential combinations of a set (meaning one or more) of valid signed transactions could be joined together by a record keeper to create a seemingly valid record. For instance, some transfers could simply be omitted or censored.
It is also possible for two transactions to each be individually valid but conflict with each other, thus giving the record keeper the choice of which to present. For instance, a digital asset owner may attempt to sell the same asset twice by signing two or more messages that each transfers the asset to a different public key. In such a case, the owner is said to be double spending her asset and the issue of double spending is referred to herein as a Double Spend problem. An untrustworthy record keeper could choose to present different versions of the record at different times or to different people such that the record, even with valid signatures, could not be relied upon.
Accordingly, a peer-to-peer digital record system that achieves agreement on the record while overcoming additional systemic challenges is desired. Such a system is referred to herein as a consensus system. As used herein, consensus refers to the process by which the entire network agrees on the same ledger. Accordingly, a consensus system is a networked system capable of reaching consensus. Network latency associated with global data transmission prevents all peers from receiving information at the same time or in the same order. Peers may disconnect and reconnect at will, data can be corrupted or missing, and some peers may intentionally supply or relay inaccurate information. These types of challenges to consensus are a long recognized problem in computer science known as a Byzantine Generals Problem. The consensus system must overcome such challenges to allow the creation of a record that can be trusted and cannot be manipulated.
Bitcoin is the most well-known attempt to tackle the problem of peer-to-peer consensus for digital token tracking. Peers on a global network will not receive all broadcasted transactions at the same time and in the same order due to, for example, network latency. Therefore, if peers were to simply accept all transactions as they were received and reject anything conflicting that came later, it would lead to disagreement. For instance, if two conflicting transactions were simultaneously broadcast, some peers would receive one transaction first and accept it, and other peers would receive the other transaction first and accept it instead, so there would no longer be a consistent record. In this case, some peers would need to switch to maintain consistency. On the other hand, it should not be possible to get the network to switch to a conflicting transaction broadcast long after the original, as this would defeat the utility of the peer-to-peer transaction system.
Bitcoin tackles this issue by grouping transactions into blocks which can generally be propagated to the whole network before a new block of transactions is produced. For example, approximately six times per hour, a new group of accepted transactions, a block, is created, added to a block chain, and quickly published to all nodes on the transaction network system. The rate of this block production is limited by requiring inclusion of a difficult to find solution to a cryptographic function based on the block data. If valid solutions are found too quickly, the size of the range of valid solutions adjusts to be more restrictive to increase the difficulty and maintain a reasonably steady rate of block production. Each block references and builds off a previous block using cryptographic functions called hashes. A hash function takes arbitrary digital data as input and returns a fixed length pseudo random number as output. To solve a block, an additional piece of data must be found that when combined with block data and data that links to the previous block generates hash function output that falls within a very restrictive range set by the protocol. Tying each block to its previous block with these hash functions generates what is known as a block chain containing all accepted transactions. A block chain thus forms a public record of all transactions. A current ledger representing the state of ownership of digital tokens can be deduced from the full record of transactions in a block chain beginning with the first block. In a block chain, each block contains a cryptographic hash of the immediate previous block or a similar reference that links it to the immediate previous block. If any data is changed or missing, the calculated cryptographic hashes would change for all blocks from that point forward. The changed hashes would also no longer fall within the restrictive range required by the Bitcoin protocol, so the chain would be invalid.
A valid solution to a block is called a proof of work (“PoW”) and the process of finding these solutions is called mining. In other words, mining is the activity of verifying and recording payments into the public ledger. The miner of a block accepted by the network is rewarded in the form of Bitcoin transaction fees from included transactions in addition to a fixed block reward. Only the longest block chain that includes the most PoW is accepted by the network as the consensus block chain. If more than one block solution is found at the same time only one of these blocks can ultimately be accepted, as each block in the chain must reference the preceding block. Other miners must choose to work on a solution that builds off one of these two available blocks and the next published block will make one block chain longer than the other. The shorter chain is then rejected by the network and its miner cannot redeem the block reward.
Miners try to make sure they are always working on the longest known chain in order to ensure that any block found is accepted in the longest chain (also referred to herein as LC) to get the reward. Miners will quickly abandon any shorter chains to avoid expending work without reward. This creates a cooperative process where self-interested miners must cooperate to extend a single longest chain. The longer the chain becomes that builds on an included transaction the more difficult it is to change that transaction. Changing the transaction would require building a longer chain with more proof of work than the public chain. Considering the public chain is built via a cooperative process of miners all over the world, building a longer chain is not an easy task. To create a longer chain in secret in order to change a transaction (such as Double Spend) would essentially require controlling more computation power than the rest of the network combined. It is assumed to be unlikely that any party will control more computation power than the rest of the network adding to the public chain.
Bitcoin's PoW consensus algorithm (also referred to herein as protocol) however, has drawbacks. As the value of Bitcoin has grown, Bitcoin mining has become very competitive. Rather than a decentralized network of people performing PoW using their personal computers, huge warehouses with specialized hardware have been set up to maximize efficiency. Mining pools have been created so operators can pool their PoW together to share block rewards and reduce the uncertainty of reward payouts. PoW also relies on arbitrarily difficult computation and the difficulty is automatically increased if solutions are found too quickly. This computation for the sake of proving computation consumes an enormous amount of electricity. Economies of scale in PoW mining have also allowed control over the Bitcoin ledger to be more centralized than originally anticipated. Therefore, there is a high demand for more efficient algorithms to achieve consensus on a signed shared ledger over a decentralized computer network.
Many attempts have been made to find better PoW algorithms that are more conducive to being solved using standard consumer computing equipment and more resistant to the creation of cheap specialized mining hardware. The Litecoin™ project (Litecoin.org) is an example of such an attempt. These attempts have only delayed the creation of specialized mining hardware and still suffer the same centralization problems due to economies of scale. Specialized hardware is now available for mining Litecoin™. The solution of using a different PoW algorithm also does not address issues of energy waste.
A number of other strategies to consensus have been proposed or are being developed. These recent consensus algorithms are often implemented in popular crypto-currencies. Crypto-currencies that employ the recently proposed consensus algorithms include Ripple™ (proposed by Ripple Labs), Peercoin (also known as PPCoin or PPC), NXT (an open source cryptocurrency and payment network launched in November 2013 by anonymous software developer BCNext), and BitShares (a decentralized exchange network system proposed by Bitshares.org).
The Ripple™ network uses a consensus algorithm that does not rely on PoW. Ripple™ protocol utilizes peer-to-peer nodes that accept transactions and confirm them after a high level of agreement is reached among their peers. A drawback to the Ripple™ consensus algorithm is that the interests of the validating nodes are not necessarily tied to or aligned with the interests of the holders and users (also referred to herein as stakeholders) of the digital currency. The currency holders must trust the validating nodes not to collude but they have no effective power to prevent it. The selection of validating nodes is not done by currency holders.
Stellar™, which is a project (stellar.org) that branched off of the Ripple™ project and uses a very similar consensus algorithm, recently experienced a fork of its payment network where consensus broke down and was not achieved throughout the network. The Stellar project has moved to a central validating authority while it works to improve its consensus algorithm.
A shared concept behind a number of recently proposed consensus protocols is called proof of stake (“PoS”) as opposed to PoW. With PoW, the ability to extend the transaction ledger is proportional to computing power. The idea behind PoS is to make control of the public ledger proportional to ownership stake of the digital currency. It is hoped that PoS will be more energy efficient and more appropriately distribute control over the ledger. A number of PoS systems are structured in a similar way to PoW mining. Just as in PoW mining, PoS mining (also called staking, minting, or forging) requires finding blocks whose block hash falls within a restrictive range; the inclusion of a block in the consensus chain entitles the PoS miner to a block reward. However, the difficulty of finding a valid block hash or the range of valid solutions depends on the ownership stake controlled by the miner. Both Peercoin and NXT utilize such a system where stakeholders use their stake to mine for blocks.
There are numerous drawbacks to this method of consensus as well. Unlike with PoW mining, PoS does not incur a substantial amount of cost to looking for block solutions that are not on the current longest chain. Therefore, creating a longer chain than the current longest public chain might be more likely as there is less cost to look for it. Such a drawback to PoS protocols is known as the Nothing at Stake problem. Another drawback to the PoS model is that it requires the private key of a miner to remain unencrypted on a network connected computer.
The original design of both the NXT and Peercoin PoS consensus mechanisms require stakeholders to keep private keys unencrypted and on a network connected computer in order to attempt to sign blocks using the private keys. This requirement poses a security risk in that a network connected computer is vulnerable to being remotely compromised and the private key could be stolen. The gold standard for carefully protecting stake in a cryptocurrency system is to generate a private key/public key pair on an offline computer; funds can be sent to a party associated with this public key even though the private key has never been on a computer connected to the Internet. It is generally not worth the risk, effort, or cost for small stakeholders to run a computer to look for block solutions using their private keys. So such systems tend to become more centrally controlled than desired. In order to address this issue, the NXT project implemented a system called Leased Forging where block signing rights could be delegated to another key separate from the private key that otherwise controls transfer of funds. Recently, the same system is planned to be implemented in Peercoin protocol. Unfortunately this process opens up a new and significant issue for the consensus algorithm.
Leased block signing rights create a condition which economists term as Market Failure. A rationally self-interested stakeholder will lease stake to the highest bidder rather than to the block signer that may be most trusted or the best for the network as a whole. Leasing to the highest bidder can also lead to centralized control of the ledger by the highest bidder. The incentives of this entity(s) may not align with other stakeholders. For example, such an entity may be attempting to double spend transactions or want to control the network for another reason. The NXT protocol attempts to address this issue with limits to the amount of stake that can be leased to a single public key. Such limits are commonly accepted as sufficient to address the issue; and the NXT project has otherwise been accepting of profit sharing or “lease to the highest bidder” behavior. In reality many public keys can be controlled by a single entity and such limits to ensure decentralization are easy to circumvent.
In April of 2014, Daniel Larimer, a founder of the BitShares project proposed a consensus algorithm called Delegated Proof of Stake (“DPOS”). The design allowed anyone to delegate his stake to another public key (meaning associating the delegated stake with the public key) for the purpose of block signing. The top 101 public keys with the most stake delegated to them would take turns producing blocks. Anyone who controls one of these 101 public keys is called a “delegate” and is charged with producing and signing blocks with the corresponding private key. Block production is grouped into rounds. The order of delegate block production within a round is randomized. Each round, delegates publish a hash of a secret random number and also reveal the secret random number that was used to generate the hash published in the previous round. These revealed secrets are hashed together to get a random number that can be used to randomize the order of delegates in the following round. The use of hashes forces delegates to commit to their random number before knowing what the other random numbers will be and as long as at least one delegate is honest about keeping their random number secret this will be an effective way to randomize the block production within the round.
This DPOS design suffers a similar issue to NXT's Leased Forging; it encourages “delegation to the highest bidder” in the same way that NXT's Leased Forging encourages “leasing to the highest bidder”. In other words, it does not lead to broadly trusted block signers. Delegating stake to a delegate can be thought of as voting for a block signer. It was suggested that if stakeholders were allowed to vote either for or against candidate block signers (weighted by their stake) this could allow stakeholders to remove an untrustworthy block signer. Unfortunately this proposal did not solve the poor incentives that lead to block signing power going to the highest bidder. As proposed, voting against block signers who pay for votes would have a high opportunity cost over voting for them and sharing in any profit. It would also be largely ineffective against candidate block signers who could switch to a new public key after accumulating too many negative votes. Thus voting against a delegate could become a game of “cat and mouse” involving constant pursuit.
There are at least two additional major limitations to most cryptocurrencies such as Bitcoin. These commonly acknowledged drawbacks are price volatility and also a lack of an effective means to fund ongoing development of a cryptocurrency protocol. While Bitcoin has useful properties such as being easy and inexpensive to transfer, its price volatility makes it risky to hold and difficult to use for everyday pricing and payments. A digital token with the properties and advantages of crypto-currencies that maintain price parity with a globally adopted currency such as the US Dollar (“USD”) could be more convenient for most commerce. Attempts to address the price volatility of Bitcoin have primarily focused on using digital tokens to represent an asset held by a particular party or institution. These tokens, sometimes called colored coins can be thought of as a tradeable “I owe you” (“IOU”) on a block chain. A drawback to this idea is that there is significant centralized counterparty risk. The digital token's value is dependent on it being honored by a particular party in exchange for another asset.
Funding the ongoing development of a digital token tracking system has been a difficult problem to solve. Often the projects are computer software open source development projects and rely on volunteers for development. Essentially, the present decentralized systems have no mechanism to effectively centralize the resources needed to incentivize developers of the system. Ongoing development of a project such as Bitcoin is an economic “public good” problem. In the past, ongoing funding for development has been provided by donations from non-profit organizations, large stakeholders, or companies that use the system such as a company that sells Bitcoin related services. Recently, “assurance contracts” have begun to be used for fundraising whereby a specific fundraising target must be reached otherwise donations are returned. Although this may offer some improvement it has not been sufficient to provide a substantial funding source. Even when considering high value systems such as Bitcoin, resources to directly fund development have been scarce. A great number of smaller projects have been abandoned or remain underdeveloped due to this issue.
Peer-to-peer systems for tracking digital records must reach consensus in the face of network latency, data corruption, and various intentional methods to manipulate or disrupt the system. One of the most important challenges of peer-to-peer digital record keeping is to determine how block signers are chosen to add transactions to the public record. Prior consensus mechanisms have not solved the issue of how to choose the most qualified and trusted block signers from a decentralized network of rationally self-interested stakeholders. Some systems such as Bitcoin and Ripple have disenfranchised stakeholders by deferring to another metric such as computation power or inclusion in a unique node list. Other PoS implementations fail to create the right incentives for appropriate control of block signing power and the public record.
Accordingly, there is a need for a new peer-to-peer consensus system that provides verifiable signatures and maintains a ledger that is consistent among all participants of the networked system. The new system achieves consensus with less power consumption. In addition, the new system achieves consensus despite network latency, data corruption and other issues. In addition the new system maintains a ledger that is resistant to Double Spend or other intentional manipulation. Furthermore, the new peer-to-peer consensus system overcomes the drawbacks of price volatility and promotes funding for development of the underlying project.